package myjava.algorithm;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Hashtable;


// Definition for singly-linked list.
 class ListNode {
     int val;
     ListNode next;
     ListNode(int x) {
         val = x;
         next = null;
     }
}


public class InterSectionOfTwoLinkedList {
	
	 public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
		 if(headA == null || headB == null) return null;
		 
		 HashSet<ListNode> hashSet = new HashSet<ListNode>();
		 
		 ListNode p1 = headA;
		 ListNode p2 = headB;
		 
		 for(;;)
		 {
			 if(p1 == null) break;
			 
			 hashSet.add(p1);
			 
			 p1 = p1.next;
		 }
		 
		 for(;;)
		 {
			 if(p2 == null) break;
			 
			 if(hashSet.contains(p2))
				 return p2;
			 
			 p2 = p2.next;
		 }
		 
	     return null;
	 }
	
	public static void main(String[] args)
	{
		
	}
}
